function BinarySearchTree() {
  function Node(key) {
    this.key = key
    this.left = null
    this.right = null
  }

  this.root = null

  BinarySearchTree.prototype.insert = (key) => {
    var newNode = new Node(key)
    if (this.root == null) {
      this.root = newNode
    } else {
      this.insertNode(this.root, newNode)
    }
  }

  // 内部调用方法
  BinarySearchTree.prototype.insertNode = (node, newNode) => {
    if (newNode.key < node.key) { //向左查找
      if (node.left == null) {
        node.left = newNode
      } else {
        this.insertNode(node.left, newNode)
      }
    } else {
      if (node.right == null) {
        node.right = newNode
      } else {
        this.insertNode(node.right, newNode)
      }
    }
  }

  // 先序遍历
  BinarySearchTree.prototype.preOrderTraversal = (handler) => {
    this.preOrderTraversalNode(this.root, handler)
  }
  BinarySearchTree.prototype.preOrderTraversalNode = (node, handler) => {
    if (node !== null) {
      handler(node.key)
      this.preOrderTraversalNode(node.left, handler)
      this.preOrderTraversalNode(node.right, handler)
    }
  }

  // 中序遍历
  BinarySearchTree.prototype.midOrderTraversal = (handler) => {
    this.midOrderTraversalNode(this.root, handler)
  }
  BinarySearchTree.prototype.midOrderTraversalNode = (node, handler) => {
    if (node != null) {
      this.midOrderTraversalNode(node.left, hander)
      handler(node.key)
      this.midOrderTraversalNode(node.right, handler)
    }
  }

  BinarySearchTree.prototype.postOrderTraversal = (handler) => {
    this.postOrderTraversalNode(this.root, handler)
  }
  BinarySearchTree.prototype.postOrderTraversalNode = (node, handler) => {
    if (node != null) {
      this.postOrderTraversalNode(node.left, handler)
      this.postOrderTraversalNode(node.right, handler)
      hander(node.key)
    }
  }
  BinarySearchTree.prototype.min = () => {
    var node = this.root
    while (node.left !== null) {
      node = node.left
    }
    return node.key
  }
  BinarySearchTree.prototype.max = () => {
    var node = this.root
    while (node.right !== null) {
      node = node.right
    }
    return node.key
  }
  BinarySearchTree.prototype.search = (key) => {
    return this.searchNode(this.root, key)
  }
  BinarySearchTree.prototype.searchNode = (node, key) => {
    if (node == null) {
      return false
    }
    if (node.key > key) {
      return this.searchNode(node.left, key)
    } else if (node.key < key) {
      return this.searchNode(node.right, key)
    } else {
      return true
    }
  }
  BinarySearchTree.prototype.remove = function (key) {
    var current = this.root
    var parent = this.root
    var isLeftChild = true

    while (current.key !== key) {
      parent = current
      if (key < current.key) {
        isLeftChild = true
        current = current.left
      } else {
        isLeftChild = false
        current = current.right
      }

      if (current === null) return false
    }
    // 删除叶子节点
    if (current.left == null && current.right == null) {
      if (current == this.root) {
        this.root = null
      } else if (!isLeftChild) {
        parent.left = null
      } else {
        parent.right = null
      }
    }
    //  删除的节点有一个子节点
    else if (current.right == null) {
      if (current == this.root) {
        this.root = current.left
      } else if (isLeftChild) {
        parent.left = current.left
      } else {
        parent.right = current.left
      }
    } else if (current.left == null) {
      if (current == this.root) {
        this.root = current.left
      } else if (isLeftChild) {
        parent.left = current.left
      } else {
        parent.right = current.left
      }
    }
    // 删除节点有两个子节点
    else {
      // 获取后继节点
      var successor = this.getSuccessor(current)

      if (current == this.root) {
        this.root = successor
      }
      // 将删除节点的左子树
      successor.left = current.left

    }
  }

  BinarySearchTree.prototype.getSuccessor = (delNode) => {
    // 定义变量 保存找到的后继
    var successor = delNode
    var current = delNode.right
    var successorParent = delNode

    while (current != null) {
      successorParent = successor
      successor = current
      current = current.left
    }
    // 判断寻找到的后继节点是否直接就是delNode的right节点
    if (successor != delNode.right) {
      successorParent.left = successor.right
      successor.right = delNode.right
    }
  }
}

var bst = new BinarySearchTree()
bst.insert(11)
bst.insert(12)
bst.insert(14)
bst.insert(1)
bst.insert(6)
bst.insert(7)
bst.insert(3)
bst.insert(8)
bst.insert(13)
bst.insert(17)
bst.insert(21)
bst.insert(34)
bst.insert(5)
bst.insert(9)

var resultString = ""
bst.preOrderTraversal((key) => {
  resultString += key + ' '
})
resultString = ""
bst.midOrderTraversal((key) => {
  resultString += key + ' '
})
resultString = ""
bst.postOrderTraversal((key) => {
  resultString += key + ' '
})